home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / glibc-1.09 / glibc-1 / glibc-1.09.1 / hurd / hurdmalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-18  |  8.7 KB  |  387 lines
  1. #include <stdlib.h>
  2. #include "hurdmalloc.h"        /* XXX see that file */
  3.  
  4. #include <gnu-stabs.h>
  5. text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
  6. text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
  7. text_set_element (_hurd_fork_child_hook, malloc_fork_child);
  8. text_set_element (_hurd_preinit_hook, malloc_init);
  9.  
  10.  
  11. /* 
  12.  * Mach Operating System
  13.  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
  14.  * All Rights Reserved.
  15.  * 
  16.  * Permission to use, copy, modify and distribute this software and its
  17.  * documentation is hereby granted, provided that both the copyright
  18.  * notice and this permission notice appear in all copies of the
  19.  * software, derivative works or modified versions, and any portions
  20.  * thereof, and that both notices appear in supporting documentation.
  21.  * 
  22.  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  23.  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  24.  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  25.  * 
  26.  * Carnegie Mellon requests users of this software to return to
  27.  * 
  28.  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  29.  *  School of Computer Science
  30.  *  Carnegie Mellon University
  31.  *  Pittsburgh PA 15213-3890
  32.  * 
  33.  * any improvements or extensions that they make and grant Carnegie Mellon
  34.  * the rights to redistribute these changes.
  35.  */
  36. /*
  37.  * HISTORY
  38.  * $Log: hurdmalloc.c,v $
  39.  * Revision 1.5  1994/06/04  01:48:44  roland
  40.  * entered into RCS
  41.  *
  42.  * Revision 2.7  91/05/14  17:57:34  mrt
  43.  *     Correcting copyright
  44.  * 
  45.  * Revision 2.6  91/02/14  14:20:26  mrt
  46.  *     Added new Mach copyright
  47.  *     [91/02/13  12:41:21  mrt]
  48.  * 
  49.  * Revision 2.5  90/11/05  14:37:33  rpd
  50.  *     Added malloc_fork* code.
  51.  *     [90/11/02            rwd]
  52.  * 
  53.  *     Add spin_lock_t.
  54.  *     [90/10/31            rwd]
  55.  * 
  56.  * Revision 2.4  90/08/07  14:31:28  rpd
  57.  *     Removed RCS keyword nonsense.
  58.  * 
  59.  * Revision 2.3  90/06/02  15:14:00  rpd
  60.  *     Converted to new IPC.
  61.  *     [90/03/20  20:56:57  rpd]
  62.  * 
  63.  * Revision 2.2  89/12/08  19:53:59  rwd
  64.  *     Removed conditionals.
  65.  *     [89/10/23            rwd]
  66.  * 
  67.  * Revision 2.1  89/08/03  17:09:46  rwd
  68.  * Created.
  69.  * 
  70.  *
  71.  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
  72.  *    Changed realloc() to copy min(old size, new size) bytes.
  73.  *    Bug found by Mike Kupfer at Olivetti.
  74.  */
  75. /*
  76.  *     File:     malloc.c
  77.  *    Author: Eric Cooper, Carnegie Mellon University
  78.  *    Date:    July, 1988
  79.  *
  80.  *     Memory allocator for use with multiple threads.
  81.  */
  82.  
  83.  
  84. #include <cthreads.h>
  85. #include "cthread_internals.h"
  86.  
  87. /*
  88.  * C library imports:
  89.  */
  90. extern bcopy();
  91.  
  92. /*
  93.  * Structure of memory block header.
  94.  * When free, next points to next block on free list.
  95.  * When allocated, fl points to free list.
  96.  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
  97.  */
  98. typedef union header {
  99.     union header *next;
  100.     struct free_list *fl;
  101. } *header_t;
  102.  
  103. #define MIN_SIZE    8    /* minimum block size */
  104.  
  105. typedef struct free_list {
  106.     spin_lock_t lock;    /* spin lock for mutual exclusion */
  107.     header_t head;        /* head of free list for this size */
  108. #ifdef    DEBUG
  109.     int in_use;        /* # mallocs - # frees */
  110. #endif    DEBUG
  111. } *free_list_t;
  112.  
  113. /*
  114.  * Free list with index i contains blocks of size 2^(i+3) including header.
  115.  * Smallest block size is 8, with 4 bytes available to user.
  116.  * Size argument to malloc is a signed integer for sanity checking,
  117.  * so largest block size is 2^31.
  118.  */
  119. #define NBUCKETS    29
  120.  
  121. static struct free_list malloc_free_list[NBUCKETS];
  122.  
  123. /* Initialization just sets everything to zero, but might be necessary on a
  124.    machine where spin_lock_init does otherwise, and is necessary when
  125.    running an executable that was written by something like Emacs's unexec.
  126.    It preserves the values of data variables like malloc_free_list, but
  127.    does not save the vm_allocate'd space allocated by this malloc.  */
  128.  
  129. static void
  130. malloc_init (void)
  131. {
  132.   int i;
  133.   for (i = 0; i < NBUCKETS; ++i)
  134.     {
  135.       spin_lock_init (&malloc_free_list[i].lock);
  136.       malloc_free_list[i].head = NULL;
  137. #ifdef DEBUG
  138.       malloc_free_list[i].in_use = 0;
  139. #endif
  140.     }
  141. }
  142.  
  143. static void
  144. more_memory(size, fl)
  145.     int size;
  146.     register free_list_t fl;
  147. {
  148.     register int amount;
  149.     register int n;
  150.     vm_address_t where;
  151.     register header_t h;
  152.     kern_return_t r;
  153.  
  154.     if (size <= vm_page_size) {
  155.         amount = vm_page_size;
  156.         n = vm_page_size / size;
  157.         /*
  158.          * We lose vm_page_size - n*size bytes here.  */
  159.     } else {
  160.         amount = size;
  161.         n = 1;
  162.     }
  163.     MACH_CALL(vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE), r);
  164.     h = (header_t) where;
  165.     do {
  166.       h->next = fl->head;
  167.       fl->head = h;
  168.       h = (header_t) ((char *) h + size);
  169.     } while (--n != 0);
  170. }
  171.  
  172. /* Declaration changed to standard one for GNU.  */
  173. void *
  174. malloc(size)
  175.     register size_t size;
  176. {
  177.     register int i, n;
  178.     register free_list_t fl;
  179.     register header_t h;
  180.  
  181.     if ((int) size < 0)        /* sanity check */
  182.         return 0;
  183.     size += sizeof(union header);
  184.     /*
  185.      * Find smallest power-of-two block size
  186.      * big enough to hold requested size plus header.
  187.      */
  188.     i = 0;
  189.     n = MIN_SIZE;
  190.     while (n < size) {
  191.         i += 1;
  192.         n <<= 1;
  193.     }
  194.     ASSERT(i < NBUCKETS);
  195.     fl = &malloc_free_list[i];
  196.     spin_lock(&fl->lock);
  197.     h = fl->head;
  198.     if (h == 0) {
  199.         /*
  200.          * Free list is empty;
  201.          * allocate more blocks.
  202.          */
  203.         more_memory(n, fl);
  204.         h = fl->head;
  205.         if (h == 0) {
  206.             /*
  207.              * Allocation failed.
  208.              */
  209.             spin_unlock(&fl->lock);
  210.             return 0;
  211.         }
  212.     }
  213.     /*
  214.      * Pop block from free list.
  215.      */
  216.     fl->head = h->next;
  217. #ifdef    DEBUG
  218.     fl->in_use += 1;
  219. #endif    DEBUG
  220.     spin_unlock(&fl->lock);
  221.     /*
  222.      * Store free list pointer in block header
  223.      * so we can figure out where it goes
  224.      * at free() time.
  225.      */
  226.     h->fl = fl;
  227.     /*
  228.      * Return pointer past the block header.
  229.      */
  230.     return ((char *) h) + sizeof(union header);
  231. }
  232.  
  233. /* Declaration changed to standard one for GNU.  */
  234. void
  235. free(base)
  236.     void *base;
  237. {
  238.     register header_t h;
  239.     register free_list_t fl;
  240.     register int i;
  241.  
  242.     if (base == 0)
  243.         return;
  244.     /*
  245.      * Find free list for block.
  246.      */
  247.     h = (header_t) (base - sizeof(union header));
  248.     fl = h->fl;
  249.     i = fl - malloc_free_list;
  250.     /*
  251.      * Sanity checks.
  252.      */
  253.     if (i < 0 || i >= NBUCKETS) {
  254.         ASSERT(0 <= i && i < NBUCKETS);
  255.         return;
  256.     }
  257.     if (fl != &malloc_free_list[i]) {
  258.         ASSERT(fl == &malloc_free_list[i]);
  259.         return;
  260.     }
  261.     /*
  262.      * Push block on free list.
  263.      */
  264.     spin_lock(&fl->lock);
  265.     h->next = fl->head;
  266.     fl->head = h;
  267. #ifdef    DEBUG
  268.     fl->in_use -= 1;
  269. #endif    DEBUG
  270.     spin_unlock(&fl->lock);
  271.     return;
  272. }
  273.  
  274. /* Declaration changed to standard one for GNU.  */
  275. void *
  276. realloc(old_base, new_size)
  277.         void *old_base;
  278.         size_t new_size;
  279. {
  280.     register header_t h;
  281.     register free_list_t fl;
  282.     register int i;
  283.     unsigned int old_size;
  284.     char *new_base;
  285.  
  286.     if (old_base == 0)
  287.       return malloc (new_size);
  288.  
  289.     /*
  290.      * Find size of old block.
  291.      */
  292.     h = (header_t) (old_base - sizeof(union header));
  293.     fl = h->fl;
  294.     i = fl - malloc_free_list;
  295.     /*
  296.      * Sanity checks.
  297.      */
  298.     if (i < 0 || i >= NBUCKETS) {
  299.         ASSERT(0 <= i && i < NBUCKETS);
  300.         return 0;
  301.     }
  302.     if (fl != &malloc_free_list[i]) {
  303.         ASSERT(fl == &malloc_free_list[i]);
  304.         return 0;
  305.     }
  306.     /*
  307.      * Free list with index i contains blocks of size 2^(i+3) including header.
  308.      */
  309.     old_size = (1 << (i+3)) - sizeof(union header);
  310.     /*
  311.      * Allocate new block, copy old bytes, and free old block.
  312.      */
  313.     new_base = malloc(new_size);
  314.     if (new_base != 0)
  315.         bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
  316.     free(old_base);
  317.     return new_base;
  318. }
  319.  
  320. #ifdef    DEBUG
  321. void
  322. print_malloc_free_list()
  323. {
  324.       register int i, size;
  325.     register free_list_t fl;
  326.     register int n;
  327.       register header_t h;
  328.     int total_used = 0;
  329.     int total_free = 0;
  330.  
  331.     fprintf(stderr, "      Size     In Use       Free      Total\n");
  332.       for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
  333.          i < NBUCKETS;
  334.          i += 1, size <<= 1, fl += 1) {
  335.         spin_lock(&fl->lock);
  336.         if (fl->in_use != 0 || fl->head != 0) {
  337.             total_used += fl->in_use * size;
  338.             for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
  339.                 ;
  340.             total_free += n * size;
  341.             fprintf(stderr, "%10d %10d %10d %10d\n",
  342.                 size, fl->in_use, n, fl->in_use + n);
  343.         }
  344.         spin_unlock(&fl->lock);
  345.       }
  346.       fprintf(stderr, " all sizes %10d %10d %10d\n",
  347.         total_used, total_free, total_used + total_free);
  348. }
  349. #endif    DEBUG
  350.  
  351. static void malloc_fork_prepare()
  352. /*
  353.  * Prepare the malloc module for a fork by insuring that no thread is in a
  354.  * malloc critical section.
  355.  */
  356. {
  357.     register int i;
  358.     
  359.     for (i = 0; i < NBUCKETS; i++) {
  360.     spin_lock(&malloc_free_list[i].lock);
  361.     }
  362. }
  363.  
  364. static void malloc_fork_parent()
  365. /*
  366.  * Called in the parent process after a fork() to resume normal operation.
  367.  */
  368. {
  369.     register int i;
  370.  
  371.     for (i = NBUCKETS-1; i >= 0; i--) {
  372.     spin_unlock(&malloc_free_list[i].lock);
  373.     }
  374. }
  375.  
  376. static void malloc_fork_child()
  377. /*
  378.  * Called in the child process after a fork() to resume normal operation.
  379.  */
  380. {
  381.     register int i;
  382.  
  383.     for (i = NBUCKETS-1; i >= 0; i--) {
  384.     spin_unlock(&malloc_free_list[i].lock);
  385.     }
  386. }
  387.